package dynamic;

import java.util.Arrays;

import utils.ArrayGenerator;

public class Ex198 {
   static class Solution {
        public int rob1(int[] nums) {
            int len;
            if (nums == null || (len = nums.length) == 0) return 0;
            int[] f = new int[len];
            f[0] = nums[0];
            int max = 0;
            for (int i = 1; i < len; i++) {
                f[i] = max + nums[i];
                max = Math.max(max, f[i - 1]);
            }
            System.out.println(Arrays.toString(f));
            return Math.max(f[len - 1], f[len - 2]);
        }

        //正确的动态规划： f[i] = max(f[i - 2] + nums[i], f[i - 1]);
        public int rob2(int[] nums) {
            int len;
            if (nums == null || (len = nums.length) == 0) return 0;
            int[] f = new int[len];
            f[0] = nums[0];
            f[1] = nums[0] > nums[1] ? nums[0] : nums[1];
            int max = Math.max(f[0], f[1]); //不然len == 2会导致循环进不去
            for (int i = 2; i < len; i++) {
                f[i] = Math.max(f[i - 2] + nums[i], f[i - 1]);
                max = Math.max(max, f[i]);
            }
           return max;
        }


        //以上所有问题都没有考虑len == 1的情况

             //奇偶动态规划： f[i] = max(f[i - 2] + nums[i], f[i - 1]);
        /* 
            类似于求奇偶最大值问题：
            纯奇数求最大 纯偶数...

            但是有 奇数与偶数相引用的情况。 f[i - 2] + nums[i]  < f[i - 1] 回导致取相异的那个
            (当异向数比同向数更大，取异向数)
            f[偶] = max(f[上一个偶] + nums[i], f[上一个奇]) //本质等价于上面的答案，但是可以减少空间复杂度
        */
        
        public int rob3(int[] nums) {
            int len;
            if (nums == null || (len = nums.length) == 0) return 0;
            if (len == 1) return nums[0];
            int sumEven = nums[0];
            int sumOdd = nums[0] > nums[1] ? nums[0] : nums[1];
            for (int i = 2; i < len; i++) {
               if (i % 2 == 1) {
                   sumOdd += nums[i];
                   sumOdd = Math.max(sumOdd, sumEven);
               } else {
                   sumEven += nums[i];
                   sumEven = Math.max(sumEven, sumOdd);
               }
            }
           return Math.max(sumEven, sumOdd);
        }

   
        //正确的动态规划的空间优化： 只与上一个与上上一个有关，存储这两个即可
        public int rob(int[] nums) {
            int len;
            if (nums == null || (len = nums.length) == 0) return 0;
            if (len == 1) return nums[0];
            int lastTow = nums[0];
            int lastOne = Math.max(lastTow, nums[1]);
            int max = Math.max(lastOne, lastTow);
            for (int i = 2; i < len; i++) {
                int temp = lastOne;
                lastOne = Math.max(lastTow + nums[i], lastOne);
                lastTow = temp;
                max = Math.max(max, lastOne);
            }
           return max;
        }

        public static void main(String[] args) {
            // int[] nums = new int[] {2,1,2,4,2,2,1};
            // int[] nums = {2,7,9,3,1};
            int[] nums = {2,1,1,2};
            // int[] nums = {1,2,3,1};
            Solution s = new Solution();
            // nums = ArrayGenerator.getArray(100, 100);
            System.out.println(Arrays.toString(nums));
            int r = s.rob(nums);
            System.out.println(r);
        }
    }
}
